package com.peng.sort.radix;

import com.study.class08.Code04_RadixSort;

/**
 * 基数排序
 */
public class RadixSort {

    public static void main(String[] args) {

        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = Code04_RadixSort.generateRandomArray(maxSize, maxValue);
            int[] arr2 = Code04_RadixSort.copyArray(arr1);
            radixSort(arr1);
            Code04_RadixSort.comparator(arr2);
            if (!Code04_RadixSort.isEqual(arr1, arr2)) {
                succeed = false;
                Code04_RadixSort.printArray(arr1);
                Code04_RadixSort.printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = Code04_RadixSort.generateRandomArray(maxSize, maxValue);
        Code04_RadixSort.printArray(arr);
        radixSort(arr);
        Code04_RadixSort.printArray(arr);


    }

    private static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        //基于十进制的
        int radix = 10;
        int max = Integer.MIN_VALUE;
        for (int val : arr) {
            max = Math.max(val, max);
        }

        int bitCount = getBitCount(max);

        int[] helpArr = new int[R - L + 1];

        /*
        从低位到高位的顺序
         */
        for (int bit = 1; bit <= bitCount; bit++) {

            int[] countArr = new int[radix];

            //对数据集，当前位上出现的数的次数，统计一下
            for (int j = L; j <= R; j++) {
                try {
                    countArr[getDigitNum(arr[j], bit)]++;
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }

            /*
            得到数的次数的累加和数组
            这意味着：
            0位置表示当前位上，<=0的数有几个
            1位置表示当前位上，<=1的数有几个
            2位置表示当前位上，<=2的数有几个
             */
            for (int j = 1; j < countArr.length; j++) {
                countArr[j] = countArr[j - 1] + countArr[j];
            }

            /*
            接着，从右向左，依次看<=这个位数的有几个
            假设某个数的该位是8，count[8]此时则意味着<=8的个数有几个，假设有5个，
            那么因为我们是从右往左进行查看的，
            所以可以定位到当前数应该归属于在原数组的4位置(个数-1，即5-1)上，
            放置好后，需要把count累加和数组位置-1
             */


            try {
                for (int j = R; j >= L; j--) {
                    int digitNum = getDigitNum(arr[j], bit);
                    helpArr[--countArr[digitNum]] = arr[j];

                }
            } catch (Exception e) {
                e.printStackTrace();
            }

            for (int i = L, j = 0; i <= R; i++, j++) {
                arr[i] = helpArr[j];
            }

        }


    }

    /**
     * 数字第digit位是什么数？
     *
     * @param num
     * @return
     */
    private static int getDigitNum(int num, int digit) {
        return (int) ((num / Math.pow(10, digit - 1)) % 10);
    }


    /**
     * 数字是几位数
     *
     * @param num
     * @return
     */
    private static int getBitCount(int num) {
        int count = 0;
        while (num != 0) {
            num /= 10;
            count++;
        }
        return count;
    }

}
